#include <iostream>
#include <unordered_map>
using namespace std;
// 整体使用哈希表和双向（头尾哨兵）链表实现
struct Node {
    int key, value;
    Node* prev;
    Node* next;
    Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
class LRUCache { //最近最少使用
public:
    LRUCache(int cap) : capacity(cap) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    } 
    int get(int key) {
        if(cache.find(key) == cache.end()) {
            return -1;
        }
        moveToFront(cache[key]);
        return cache[key]->value;
    }
    void put(int key, int value) {
        if(cache.find(key) != cache.end()) {
            cache[key]->value = value;
            moveToFront(cache[key]);
        }else {
            if(cache.size() == capacity) { // 满了就删除
                removeLast();
            }
            Node* newnode = new Node(key, value);
            cache[key] = newnode;
            moveToFront(newnode);
        }
    }

private:
    int capacity;
    unordered_map<int, Node*> cache;
    Node* head;
    Node* tail;
    void moveToFront(Node* node) {
        if(node->prev) { // 判断前驱
            node->prev->next = node->next;
        }
        if(node->next) { // 判断后驱
            node->next->prev = node->prev;
        }
        node->next = head->next;
        if(head->next) { // 判断插入位置还有没有后驱
            head->next->prev = node;
        }
        head->next = node;
        node->prev = head;
    }
    void removeLast() {
        if(tail->prev == head) { // 判断是不是没有节点可以删除了
            return;
        }
        Node* temp = tail->prev; 
        if(temp->prev) { // 判断前驱是不是空
            temp->prev->next = tail;
        }
        tail->prev = temp->prev;
        cache.erase(temp->key);
        delete temp;
    }

};

int main() {
    LRUCache cache(2);

    cache.put(1, 1); // cache is {1=1}
    cache.put(2, 2); // cache is {1=1, 2=2}
    cout << cache.get(1) << endl; // returns 1, cache is {2=2, 1=1}
    cache.put(3, 3); // evicts key 2, cache is {1=1, 3=3}
    cout << cache.get(2) << endl; // returns -1 (not found)
    cache.put(4, 4); // evicts key 1, cache is {3=3, 4=4}
    cout << cache.get(1) << endl; // returns -1 (not found)
    cout << cache.get(3) << endl; // returns 3, cache is {4=4, 3=3}
    cout << cache.get(4) << endl; // returns 4, cache is {3=3, 4=4}

    return 0;
}